home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1999 March / EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso / earcd / grafica / amhelios / oct_quan.cpp < prev    next >
C/C++ Source or Header  |  1999-01-01  |  8KB  |  327 lines
  1. ////////////////////////////////////////////////////////////
  2. //
  3. //  OCT_QUAN.CPP - Octree Color Quantization Class
  4. //
  5. //  Version:    1.03A
  6. //
  7. //  History:    94/08/23 - Version 1.00A release.
  8. //              94/11/10 - Modified InsertNode to properly
  9. //                         mark nodes as reducible.
  10. //              94/11/11 - Version 1.00B release.
  11. //              94/11/27 - Converted to MS-Windows
  12. //                         environment.
  13. //              94/12/16 - Version 1.01A release.
  14. //              95/02/05 - Version 1.02A release.
  15. //              95/07/21 - Version 1.02B release.
  16. //              96/02/14 - Version 1.02C release.
  17. //              96/04/01 - Version 1.03A release.
  18. //
  19. //  Compilers:  Microsoft Visual C/C++ Professional V1.5
  20. //              Borland C++ Version 4.5
  21. //
  22. //  Author:     Ian Ashdown, P.Eng.
  23. //              byHeart Software Limited
  24. //              620 Ballantree Road
  25. //              West Vancouver, B.C.
  26. //              Canada V7S 1W3
  27. //              Tel. (604) 922-6148
  28. //              Fax. (604) 987-7621
  29. //
  30. //  Copyright 1994-1996 byHeart Software Limited
  31. //
  32. //  The following source code has been derived from:
  33. //
  34. //    Ashdown, I. 1994. Radiosity: A Programmer's
  35. //    Perspective. New York, NY: John Wiley & Sons.
  36. //
  37. //  It may be freely copied, redistributed, and/or modified
  38. //  for personal use ONLY, as long as the copyright notice
  39. //  is included with all source code files.
  40. //
  41. ////////////////////////////////////////////////////////////
  42.  
  43. #include "oct_quan.h"
  44.  
  45. // Write device-independent bitmap (DIB) to file
  46. // Quantize 24-bit RGB color bitmap
  47. BOOL OctQuant::Quantize()
  48. {
  49.   if (BuildTree() == FALSE)     // Build octree
  50.     return FALSE;
  51.  
  52.   // Initialize number of quantized colors
  53.   num_colors = 0;
  54.  
  55.   // Set color palette entries
  56.   FillPalette(proot, &num_colors);
  57.  
  58.   // Map 24-bit RGB colors to 8-bit color palette entries
  59.   MapColors();
  60.  
  61.   DeleteTree();     // Delete octree
  62.  
  63.   return TRUE;
  64. }
  65.  
  66. void OctQuant::DeleteTree()     // Delete octree
  67. {
  68.   int i;        // Loop index
  69.  
  70.   // Clear the reducible node list pointers
  71.   for (i = 0; i < leaf_level; i++)
  72.     prnl[i] = NULL;
  73.  
  74.   if (proot != NULL)    // Release octree nodes
  75.   {
  76.     DeleteNode(proot);
  77.     proot = NULL;
  78.   }
  79.  
  80.   // Reset octree leaf level
  81.   leaf_level = O_MaxDepth + 1;
  82.  
  83. }
  84.  
  85. BOOL OctQuant::BuildTree()      // Build octree
  86. {
  87.   int row;              // Row counter
  88.   int col;              // Column counter
  89.   BOOL status = TRUE;   // Return status
  90.   ColorRGB color;       // Pixel color
  91.  
  92.   // Allocate octree root node
  93.   if ((proot = MakeNode(0)) == NULL)
  94.     status = FALSE;
  95.  
  96.   // Build the octree
  97.   if (status == TRUE)
  98.   {
  99.     for (row = 0; row < height; row++)
  100.     {
  101.       for (col = 0; col < width; col++)
  102.       {
  103.         GetPixel(col, row, &color);
  104.  
  105.         // Insert pixel color into octree
  106.         if (InsertNode(proot, color) == FALSE)
  107.         {
  108.           DeleteNode(proot);      // Delete the octree
  109.           status =  FALSE;
  110.           break;
  111.         }
  112.  
  113.         // Reduce octree if too many colors
  114.         if (num_leaf > max_colors)
  115.           ReduceTree();
  116.       }
  117.  
  118.       if (status == FALSE)
  119.         break;
  120.     }
  121.   }
  122.  
  123.   return status;
  124. }
  125.  
  126. // Recursively delete octree nodes
  127. void OctQuant::DeleteNode( OctNode *pn )
  128. {
  129.   int i;        // Loop index
  130.   OctNode *pc;  // Child node pointer
  131.  
  132.   if (pn == NULL)
  133.     return;
  134.  
  135.   if (pn->IsLeaf() == FALSE)
  136.   {
  137.     // Delete child nodes
  138.     for (i = 0; i < 8; i++)
  139.     {
  140.       if ((pc = pn->GetChild(i)) != NULL)
  141.       {
  142.         DeleteNode(pc);
  143.         pn->SetChild(i, NULL);
  144.         pn->DecNumChild();
  145.       }
  146.     }
  147.   }
  148.   else
  149.     num_leaf--;
  150.  
  151.   delete pn;
  152. }
  153.  
  154. // Set color palette entries
  155. void OctQuant::FillPalette( OctNode *pn, int *pindex )
  156. {
  157.   int i;    // Loop index
  158.  
  159.   // Perform recursive depth-first traversal of octree
  160.   if (pn != NULL)
  161.   {
  162.     if ((pn->IsLeaf() == TRUE) || pn->GetLevel() ==
  163.         leaf_level)
  164.     {
  165.       // Set color palette entry
  166.       palette[*pindex].SetRed(pn->GetColor().GetRed());
  167.       palette[*pindex].SetGreen(pn->GetColor().GetGreen());
  168.       palette[*pindex].SetBlue(pn->GetColor().GetBlue());
  169.  
  170.       // Set node color palette index
  171.       pn->SetIndex(*pindex);
  172.  
  173.       // Advance to next color palette entry
  174.       *pindex = *pindex + 1;
  175.     }
  176.     else
  177.     {
  178.       // Visit child nodes
  179.       for (i = 0; i < 8; i++)
  180.         FillPalette(pn->GetChild(i), pindex);
  181.     }
  182.   }
  183. }
  184.  
  185. // Get next reducible node pointer
  186. OctNode *OctQuant::GetReducible()
  187. {
  188.   int new_level;        // New reducible node level
  189.   OctNode *prn;         // Reducible node pointer
  190.   OctNode *pscn = NULL; // Smallest pixel count node
  191.   OctNode *pnext;       // Next node
  192.   OctNode *pprev;       // Previous node
  193.  
  194.   new_level = leaf_level - 1;
  195.  
  196.   // Find lowest reducible node level 
  197.   while (prnl[new_level] == NULL)
  198.     new_level--;
  199.  
  200.   // Find node with smallest pixel count
  201.   prn = prnl[new_level];
  202.   while (prn != NULL)
  203.   {
  204.     if (pscn == NULL)
  205.       pscn = prn;
  206.     else if (prn->GetCount() < pscn->GetCount())
  207.       pscn = prn;
  208.     prn = prn->GetNext();
  209.   }
  210.   
  211.   // Remove node from reducible list
  212.   pnext = pscn->GetNext();
  213.   pprev = pscn->GetPrev();
  214.   if (pprev == NULL)
  215.   {
  216.     prnl[new_level] = pnext;
  217.     if (pnext != NULL)
  218.       pnext->SetPrev(NULL);
  219.   }
  220.   else
  221.   {
  222.     pprev->SetNext(pnext);
  223.     if (pnext != NULL)
  224.       pnext->SetPrev(pprev);
  225.   }
  226.  
  227.   pscn->SetNext(NULL);
  228.   pscn->SetPrev(NULL);
  229.   pscn->SetMark(FALSE);
  230.   
  231.   return pscn;
  232. }
  233.  
  234. void OctQuant::ReduceTree()     // Reduce octree
  235. {
  236.   int i;        // Loop index
  237.   OctNode *pn;  // Node pointer
  238.   OctNode *pc;  // Child node pointer
  239.  
  240.   pn = GetReducible();  // Get next reducible node
  241.  
  242.   // Delete children
  243.   for (i = 0; i < 8; i++)
  244.   {
  245.     if ((pc = pn->GetChild(i)) != NULL)
  246.     {
  247.       DeleteNode(pc);
  248.       pn->SetChild(i, NULL);
  249.       pn->DecNumChild();
  250.     }
  251.   }
  252.  
  253.   pn->SetLeaf(TRUE);    // Mark node as leaf
  254.   num_leaf++;           // Increment leaf count
  255.  
  256.   // Update reduction and leaf levels
  257.   if (pn->GetLevel() < (leaf_level - 1))
  258.     leaf_level = pn->GetLevel() + 1;
  259. }
  260.  
  261. // Insert node into octree
  262. BOOL OctQuant::InsertNode( OctNode *pn, ColorRGB &c )
  263. {
  264.   int c_index;          // Child index
  265.   int level;            // Node level
  266.   BOOL status = TRUE;   // Return status
  267.   OctNode *pc;          // Child node pointer
  268.  
  269.   level = pn->GetLevel();       // Get node level
  270.   pn->AddColor(c);              // Add RGB color to node
  271.  
  272.   if (pn->IsLeaf() == FALSE && level < leaf_level)
  273.   {
  274.     // Find child node
  275.     c_index = pn->FindChild(c);
  276.  
  277.     if ((pc = pn->GetChild(c_index)) == NULL)
  278.     {
  279.       // Allocate child node
  280.       if ((pc = MakeNode(level + 1)) == NULL)
  281.         return FALSE;
  282.  
  283.       // Set child node pointer
  284.       pn->SetChild(c_index, pc);
  285.  
  286.       pn->IncNumChild();      // Increment child count
  287.     }
  288.  
  289.     if ((pn->GetNumChild() > 1) && (pn->IsMark() == FALSE))
  290.     {
  291.       // Mark node as candidate for reduction
  292.       MakeReducible(pn);
  293.     }
  294.  
  295.     // Insert child node into octree
  296.     status = InsertNode(pc, c);
  297.   }
  298.  
  299.   return status;
  300. }
  301.  
  302. // Map 24-bit RGB colors to 8-bit color palette entries
  303. void OctQuant::MapColors()
  304. {
  305.   int row;              // Row counter
  306.   int col;              // Column counter
  307.   BYTE qcolor;          // Quantized pixel color
  308.   ColorRGB color;       // 24-bit RGB color
  309.  
  310.   // Quantize the bitmap colors
  311.   for (row = 0; row < height; row++)
  312.   {
  313.     for (col = 0; col < width; col++)
  314.     {
  315.       // Get 24-bit RGB pixel color
  316.       GetPixel(col, row, &color);
  317.       
  318.       // Get color palette index
  319.       qcolor = QuantizeColor(proot, color);
  320.  
  321.       // Set 8-bit palette pixel color
  322.       SetPalPixel(col, row, qcolor);
  323.     }
  324.   }
  325. }
  326.  
  327.